class Scope:
    def __init__(self, left={}, right={}):
        self.left = left
        self.right = right

    def look_left(self, var):
        if var not in self.left:
            return False
        return self.left[var]

    def look_right(self, var):
        if var not in self.right:
            return False
        return self.right[var]

    def set_left(self, var, val):
        self.left[var] = val

    def set_right(self, var, val):
        self.right[var] = val

    def all_same(self, fake, val):
        for var in self.left.keys():
            if self.left[var] == fake:
                self.left[var] = val

        for var in self.right.keys():
            if self.right[var] == fake:
                self.right[var] = val
            

def val_is_var(val):
    return type(val) is str and val[0].isupper()

def val_is_const(val):
    return type(val) is str and val[0].islower()

def val_is_fake(val):
    return type(val) is str and val[0] == '_'

fake_var_cnt = 0
def fake_var():
    global fake_var_cnt
    var = '_' + str(fake_var_cnt)
    fake_var_cnt += 1
    return var                

def unify_not_var(left, right, scope):
    if type(left) is not type(right):
        return False
    
    # constants
    if val_is_const(left):
        return left == right

    # lists
    if type(left) is not list:
        return False

    if len(left) != len(right):
        return False

    for new_left, new_right in zip(left, right):
        if not unify(new_left, new_right, scope):
            return False

    return True
    

def unify(left, right, scope):
    if not val_is_var(left):
        if not val_is_var(right):
            return unify_not_var(left, right, scope)
        if not scope.look_right(right):
            scope.set_right(right, left)
            return True
        if not val_is_fake(scope.look_right(right)):
            return unify(left, scope.look_right(right), scope)
        scope.all_same(scope.look_right(right), left)
        return True

    if not scope.look_left(left):
        if not val_is_var(right):
            scope.set_left(left, right)
            return True
        if not scope.look_right(right):
            fake = fake_var()
            scope.set_left(left, fake)
            scope.set_right(right, fake)
            return True
        scope.set_left(scope.look_right(right))
        return True

    if not val_is_fake(scope.look_left(left)):
        if not val_is_var(right):
            return unify_not_var(scope.look_left(left), right, scope)
        if not scope.look_right(right):
            scope.set_right(right, scope.look_left(left))
            return True
        if not val_is_fake(scope.look_right(right)):
            return unify_not_var(scope.look_left(left), scope.look_right(right), scope)
        scope.all_same(scope.look_right(right), scope.look_left(left), scope)
        return True

    if not val_is_var(right):
        scope.all_same(scope.look_left(left), right, scope)
        return True
    if not scope.look_right(right):
        scope.set_right(right, scope.look_left(left))
        return True
    if not val_is_fake(scope.look_right(right)):
        return unify_not_var(scope.look_left(left), scope.look_right(right), scope)

    scope.all_same(scope.look_left(left), scope.look_right(right), scope)
    return True

scope = Scope()
unify(['X', ['s', 'g'], 'Y'],
      ['k', 'X', ['t', 'K']],
      scope)
print(scope.left)
print(scope.right)
